from typing import *


class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:

        def f(t):
            idx, l = [], len(t)
            for i in range(len(s) - l + 1):
                if s[i : i + l] == t:
                    idx.append(i)
            return idx

        ai = f(a)
        bi = f(b)
        ans, l, r = [], 0, 0
        for i in ai:
            while l < len(bi) and bi[l] < i - k:
                l += 1
            while r < len(bi) and bi[r] <= i + k:
                r += 1
            if r - l > 0:
                ans.append(i)
        return ans


s = Solution()
print(s.beautifulIndices("wfvxfzut", "wfv", "ut", 6))
# print(s.beautifulIndices("isawsquirrelnearmysquirrelhouseohmy", "my", "squirrel", 15))
